package aco;

/**
 * ACO algorithms for the TSP
 * <p>
 * This code is based on the ACOTSP project of Thomas Stuetzle.
 * It was initially ported from C to Java by Adrian Wilke.
 * <p>
 * Project website: http://adibaba.github.io/ACOTSPJava/
 * Source code: https://github.com/adibaba/ACOTSPJava/
 */

import java.util.ArrayList;

import aco.InOut.Distance_type;

//VRPTW是问题类，存储问题实例的相关信息
public class VRPTW {

    //maximum number of vehicle allowed for constructing the solution or the size of the vehicle fleet
    private int nrVehicles;

    //the capacity of each vehicle
    private int capacity;

    // arraylist which keeps all the customer requests defined in the VRPTW instance
    // 存储所有城市请求（包括动态和静态）
    private ArrayList<Request> requests;

    //arraylist which keeps the ids of the available requests known at the current time
    //initially it contains the ids of the apriori requests, having available time = 0
    // 当前时间点情况下的，可以处理的城市编号链表
    private ArrayList<Integer> idAvailableRequests;

    //arraylist which keeps the list of dynamic requests, which are not known in advance, having available time > 0
    // 动态请求城市的链表（随着时间进行，从此链表中动态抽取请求城市）
    private ArrayList<Request> dynamicRequests;

    //number of cities/customers, except the depot
    // n表示除仓库外，所有的城市数量
    static int n;


    // 请求城市的坐标
    static class Point {
        double x;
        double y;
    }

    // 总问题由多个时域组成，这个类表示单个时域需要处理的问题
    public static class Problem {
        String name; /* instance name */
        int n_near; /* number of nearest neighbors */
        Point[] nodes; /* array of classes containing coordinates of nodes */
        /* distance matrix: distance[i][j] gives distance，i->j的距离 */
        double[][] distance;

        // 下面是邻近城市链表。nn_list不包括仓库，nn_list_all包括仓库。
        // nn_list[i][j]表示到城市i距离第j近的城市编号
        int[][] nn_list; /* nearest neighbor list; contains for each node i a sorted list of n_near nearest neighbors */
        int[][] nn_list_all; /* nearest neighbor list; contains for each node i a sorted list of n_near nearest neighbors including the depot*/

    }

    static Problem instance;

    public VRPTW() {
    }

    public VRPTW(int nrVehicles_, int capacity_) {
        this.nrVehicles = nrVehicles_;
        this.capacity = capacity_;
    }

    public VRPTW(int nrVehicles_, int capacity_, ArrayList<Request> list) {
        this(nrVehicles_, capacity_);

        this.requests = new ArrayList<Request>(list.size());
        for (int i = 0; i < list.size(); i++) {
            this.requests.set(i, list.get(i));
        }
    }

    public int getNrVehicles() {
        return nrVehicles;
    }

    public void setNoVehicles(int nrVehicles) {
        this.nrVehicles = nrVehicles;
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    public ArrayList<Request> getRequests() {
        return requests;
    }

    public void setRequests(ArrayList<Request> requests) {
        this.requests = requests;
    }

    public ArrayList<Integer> getIdAvailableRequests() {
        return idAvailableRequests;
    }

    public void setIdAvailableRequests(ArrayList<Integer> idAvailableRequests) {
        this.idAvailableRequests = idAvailableRequests;
    }

    public ArrayList<Request> getDynamicRequests() {
        return dynamicRequests;
    }

    public void setDynamicRequests(ArrayList<Request> dynamicRequests) {
        this.dynamicRequests = dynamicRequests;
    }

    //    一个向下取整的方法，用于后面的计算距离矩阵
    static double dtrunc(double x) {
        int k;
        k = (int) x;
        x = (double) k;
        return x;
    }


//     FUNCTION: the following four functions implement different ways of computing distances for TSPLIB instances
//     INPUT: two node indices
//     OUTPUT: distance between the two nodes

    //compute Euclidean distances between two nodes rounded to next integer for TSPLIB instances(欧氏距离)
    static double euclidianDistance(int i, int j) {
        double xd = 0, yd = 0;

        xd = VRPTW.instance.nodes[i].x - VRPTW.instance.nodes[j].x;
        yd = VRPTW.instance.nodes[i].y - VRPTW.instance.nodes[j].y;

        double r = Math.sqrt(xd * xd + yd * yd);

        return r;
    }

    // 对求得的距离向上取整
    //compute ceiling distance between two nodes rounded to next integer for TSPLIB instances
    static int ceil_distance(int i, int j) {
        double xd = instance.nodes[i].x - instance.nodes[j].x;
        double yd = instance.nodes[i].y - instance.nodes[j].y;
        double r = Math.sqrt(xd * xd + yd * yd);

        return (int) Math.ceil(r);
    }

    //compute geometric distance between two nodes rounded to next integer for TSPLIB instances
    // 计算在地球上两个经纬度坐标之间的距离
    static int geo_distance(int i, int j) {
        double deg, min;
        double lati, latj, longi, longj;
        double q1, q2, q3;
        int dd;
        double x1 = instance.nodes[i].x, x2 = instance.nodes[j].x, y1 = instance.nodes[i].y, y2 = instance.nodes[j].y;

        deg = dtrunc(x1);
        min = x1 - deg;
        lati = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;
        deg = dtrunc(x2);
        min = x2 - deg;
        latj = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;

        deg = dtrunc(y1);
        min = y1 - deg;
        longi = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;
        deg = dtrunc(y2);
        min = y2 - deg;
        longj = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;

        q1 = Math.cos(longi - longj);
        q2 = Math.cos(lati - latj);
        q3 = Math.cos(lati + latj);
        dd = (int) (6378.388 * Math.acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
        return dd;
    }

    //compute ATT(Average Travel Time) distance between two nodes rounded to next integer for TSPLIB instances
    static int att_distance(int i, int j) {
        double xd = instance.nodes[i].x - instance.nodes[j].x;
        double yd = instance.nodes[i].y - instance.nodes[j].y;
        double rij = Math.sqrt((xd * xd + yd * yd) / 10.0);
        double tij = dtrunc(rij);
        int dij;

        if (tij < rij)
            dij = (int) tij + 1;
        else
            dij = (int) tij;
        return dij;
    }

    /**
     * computes the matrix of all intercity/inter customers distances
     *
     * @param scalingValue
     * @return
     */
    static double[][] compute_distances(double scalingValue) {
        int i, j;
        int size = VRPTW.n;
        //include also the depot city in the distance matrix: it will correspond to index 0 for row and column
        double matrix[][] = new double[size + 1][size + 1];

        for (i = 0; i < size + 1; i++) {
            for (j = 0; j < size + 1; j++) {
                if (InOut.distance_type == Distance_type.ATT) {
                    matrix[i][j] = att_distance(i, j);
                } else if (InOut.distance_type == Distance_type.CEIL_2D) {
                    matrix[i][j] = ceil_distance(i, j);
                } else if (InOut.distance_type == Distance_type.EUC_2D) {
                    matrix[i][j] = euclidianDistance(i, j);
//                    这里的刻度值有什么用处???scalingValue
                    if (scalingValue != 0) {
                        matrix[i][j] *= scalingValue;
                    }
                } else if (InOut.distance_type == Distance_type.GEO) {
                    matrix[i][j] = geo_distance(i, j);
                }
            }
        }
        return matrix;
    }

    /**
     * computes nearest neighbor lists of depth nn for each city
     *
     * @return result[i][j][k]
     * i=0返回m_nnear（不包括仓库）；i=1返回m_nnear_all（包括仓库）
     * j代表当前城市，result的值代表下一个城市的编号，k代表当前城市到下一个城市的顺序索引
     * result[0][1][3] = 5：不包括仓库，城市1的第3个临近城市为城市5
     */
    static int[][][] compute_nn_lists(VRPTW vrp) {
        int i, node, nn, count1, count2;

        // 几个临时存储距离的数组
        int size = VRPTW.n;
        double[] distance_vector = new double[size + 1];
        int[] help_vector = new int[size + 1];

        // nn表示，为当前城市寻找几个邻近城市
        nn = Ants.nn_ants;
        if (nn >= size + 1) nn = size - 2;
        Ants.nn_ants = nn;

        int[][][] result = new int[2][][];
        int[][] m_nnear = new int[size + 1][nn];// 不包括仓库
        int[][] m_nnear_all = new int[size + 1][nn];  //include also the depot city

        for (node = 0; node < size + 1; node++) { /* compute candidate-sets for all nodes */
            for (i = 0; i < size + 1; i++) { /* Copy distances from nodes to the others */
                distance_vector[i] = VRPTW.instance.distance[node][i]; // 城市node -> 城市i的距离
                //distance_vector[i] = 0.9 * VRPTW.instance.distance[node][i] + 0.1 * vrp.getRequests().get(i).getEndWindow();
                help_vector[i] = i; // 距离城市node第i近的城市的编号
            }
            distance_vector[node] = Integer.MAX_VALUE; /* city itself is not nearest neighbor */
            Utilities.sort2(distance_vector, help_vector, 0, size);

            // m_nnear[][]，不包括仓库的【邻近城市序列】
            count1 = 0;
            i = -1; // i = 0不行？
            while (count1 < nn) {
                i++;
                //include in the nn_list of a node only the nodes that are known (available)
                //if ((help_vector[i] != 0) && (vrp.getIdAvailableRequests().contains(i))) {
                if (help_vector[i] != 0) {
                    m_nnear[node][count1] = help_vector[i];
                    count1++;
                } else {
                    continue;
                }
            }

            // m_nnear_all[][]，包括仓库的【邻近城市序列】
            count2 = 0;
            i = -1;
            while (count2 < nn) {
                i++;
                //include in the nn_list of a node only the nodes that are known (available)
                //if (vrp.getIdAvailableRequests().contains(i)) {
                m_nnear_all[node][count2] = help_vector[i];
                count2++;
                //}

            }
        }

        //return m_nnear;
        result[0] = m_nnear;
        result[1] = m_nnear_all;
        return result;
    }

    // 从仓库出发
    //compute the tour length of tour t taking also into account the depot city
    static double compute_tour_length(ArrayList<Integer> t) {
        int i;
        double sum = 0;

        if (t.size() > 1) {
            for (i = 0; i < t.size() - 1; i++) {
                sum += VRPTW.instance.distance[t.get(i) + 1][t.get(i + 1) + 1];
            }
        }

        return sum;
    }

    // 这应该是用于测试的，一个计算路径t长度的方法，程序运行中没有用到。
    //compute the tour length of tour t taking also into account the depot city
    static double compute_tour_length1(ArrayList<Integer> t) {
        int i;
        double sum = 0;

        if (t.size() > 1) {
            for (i = 0; i < t.size() - 1; i++) {
                sum += VRPTW.instance.distance[t.get(i)][t.get(i + 1)];
            }
        }

        return sum;
    }

    // 从仓库出发，并回到仓库
    static double compute_tour_length_(ArrayList<Integer> t) {
        int i;
        double sum = 0;

        if (t.size() > 1) {
            sum += VRPTW.instance.distance[0][t.get(1) + 1];
            for (i = 1; i < t.size() - 2; i++) {
                sum += VRPTW.instance.distance[t.get(i) + 1][t.get(i + 1) + 1];
            }
            sum += VRPTW.instance.distance[t.get(t.size() - 2) + 1][0];
        }

        return sum;
    }
}